package com.sicheng.lc.周赛.分类.模拟;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/22 20:58
 */
public class 向表达式添加括号后的最小结果 {
    //https://leetcode.cn/problems/minimize-result-by-adding-parentheses-to-expression/
    public String minimizeResult(String s) {
//        输入：s = "247+38"
//        输出："2(47+38)"
        int a = 0;
        int b = 0;
        int c;
        int d;
        //拆分成4部分枚举得到最小结果   ll* (c+d) * rr
        int res = Integer.MAX_VALUE >> 1;
        int i = 0;
        for (; i < s.length(); i++) {
            if (s.charAt(i) == '+') {
                break;
            }
            a = a * 10 + s.charAt(i) - '0';
        }
        int t = i;
        for (i = i + 1; i < s.length(); i++) {
            b = b * 10 + s.charAt(i) - '0';
        }

        String ss = null;
        for (int j = t - 1; j >= 0; j--) {
            c = Integer.parseInt(s.substring(j, t));
            for (int k = t + 1; k < s.length(); k++) {
                d = Integer.parseInt(s.substring(t + 1, k + 1));
                String tt = s.substring(0, j);
                int ll = tt.equals("") ? 1 : Integer.parseInt(tt);
                int rr = k + 1 < s.length() ? Integer.parseInt(s.substring(k + 1)) : 1;
                if ((c + d) * ll * rr < res) {
                    //拆分成4部分枚举得到最小结果   ll* (c+d) * rr
                    res = (c + d) * ll * rr;
                    ss = tt + "(" + c + "+" + d + ")" + (k + 1 < s.length() ? rr : "");
                }
            }
        }
        return ss;
    }

    public static void main(String[] args) {
        向表达式添加括号后的最小结果 solution = new 向表达式添加括号后的最小结果();
        System.out.println(solution.minimizeResult("247+38"));

    }
}
